import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mac
 * Date: 2022-09-26
 * Time: 20:01
 */
class TreeNode {
    public char val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(char val) {
        this.val = val;
    }
}
public class TestDemo {
    //100.相同的树
    //O(min(m,n))
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null){
            return true;
        }
        if (p == null || q == null){
            return false;
        }
        if (p.val != q.val){
            return false;
        }
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }

    //572.另一棵树的子树
    //O(m*n)
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null || subRoot == null){
            return false;
        }
        if (isSameTree(root, subRoot)){
            return true;
        }
        if (isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot)){
            return true;
        }
        return false;
    }

    //226.翻转二叉树


    //110.平衡二叉树
    //求GAP度：O(n)

    /*public int height(TreeNode root){
        if (root == null){
            return 0;
        }
        return Math.max(height(root.left), height(root.right)) + 1;
    }
    //O(n^2)
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        int left = height(root.left);
        int right = height(root.right);

        return Math.abs(left - right) <= 1 && isBalanced(root.left) &&isBalanced(root.right);
    }*/

    //优化 整个时间复杂度O(n)
    public int height(TreeNode root){
        if (root == null){
            return 0;
        }
        int leftHight = height(root.left);
        int righthHight = height(root.right);
        if (leftHight >= 0 && righthHight >= 0 && Math.abs(leftHight - righthHight) <= 1){
            return Math.max(leftHight,righthHight) + 1;
        }else{
            //说明是否平衡
            return -1;
        }
    }
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;


        return height(root) >= 0;
    }

    //101.对称二叉树
    public boolean isSymmetricChild(TreeNode leftroot, TreeNode rightroot){
        if (leftroot == null && rightroot == null) return true;
        if (leftroot == null || rightroot == null) return false;
        if (leftroot.val != rightroot.val) return false;
        return isSymmetricChild(leftroot.left, rightroot.right) && isSymmetricChild(leftroot.right, rightroot.left);
    }
    public boolean isSymmetric(TreeNode root) {
        if (root == null){
            return true;
        }
        return isSymmetricChild(root.left, root.right);
    }

    //牛客 - KY11 二叉树构建
    public static int i = 0;
    public static TreeNode createTree(String str){
        TreeNode root = null;
        if (str.charAt(i) != '#'){
            root = new TreeNode(str.charAt(i));
            i++;
            root.left = createTree(str);
            root.right = createTree(str);
        }else{
            //遇到#号
            i++;
        }
        return root;
    }
    public static void inorder(TreeNode root){
        if (root == null){
            return;
        }
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str = in.nextLine();
            TreeNode root = createTree(str);
            inorder(root);
        }
    }

    //102.二叉树的层序遍历
    public void levelOrder(TreeNode root){
        if (root == null){
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (queue.peek() != null){
            TreeNode cur = queue.poll();
            System.out.print(cur.val + " ");//打印每层节点
            if (cur != null){
                if (cur.left != null) {//不为空入队
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
        }
    }
    public List<List<Integer>> levelOrder1(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if (root == null) return ret;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);


        while (!queue.isEmpty()){
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            while (size != 0){
                TreeNode cur = queue.poll();
                //list.add(cur.val);
                if (cur.left != null) {//不为空入队
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
                size--;
            }
            ret.add(list);
        }
        return ret;
    }
}
